package com.lft.linked.list01.single_linked_list;

import java.util.Stack;

/**
 * 单链表工具类，链表中不区别头节点。
 */
public class SingleLinkedListUtil {
	/**
	 * 【普通添加】
	 * 添加节点到单向链表
	 * 思路(不考虑编号顺序时)：
	 * 1. 找到当前链表的最后节点
	 * 2. 将最后这个节点的 next 指向新的节点。
	 * @param originalHead 原始链表节点头
	 * @param newNode      需要添加的新节点
	 * @return 返回添加后的节点
	 */
	public static HeroNode add(HeroNode originalHead, HeroNode newNode) {
		// 1. 判断一下链表是否为空
		if (originalHead == null) {
			System.out.println("原始链表为空");
			return newNode;
		}
		if (newNode == null) {
			// System.out.println("要添加的节点为空");
			return originalHead;
		}
		
		// 因为 head 节点不能动，所以需要一个辅助变量(指针) temp
		HeroNode temp = originalHead;
		
		// 遍历链表，找到最后。当退出while循环时，temp就是指向了链表的最后
		// 找到链表的最后
		while (temp.next != null) {
			// 如果没有找到，就将temp后移
			temp = temp.next;
		}
		// 将最后这个节点的 next 指向新的节点。
		temp.next = newNode;
		return originalHead;
	}
	
	/**
	 * 【按顺序添加】
	 * 第二种方式添加英雄时，根据排名将英雄插入到指定位置
	 * (如果有这个排名，则添加失败，并给出提示)
	 * @param originalHead 原始链表节点头
	 * @param newNode      需要添加的节点。
	 * @return 返回添加后的节点
	 */
	public static HeroNode addByOrder(HeroNode originalHead, HeroNode newNode) {
		// 1. 判断一下链表是否为空
		if (originalHead == null) {
			System.out.println("链表为空");
			return newNode;
		}
		if (newNode == null) {
			// System.out.println("要添加的节点为空");
			return originalHead;
		}
		
		// 因为 head 节点不能动，所以需要一个辅助变量(指针) temp来帮助找到添加的位置。
		// 因为单链表，temp是位于添加位置的前一个节点，否则加入不了。
		HeroNode temp = originalHead;
		
		// 标志添加的编号是否存在，默认false不存在。
		boolean flag = false;
		
		while (temp.next != null) {
			if (temp.next.no > newNode.no) {
				// temp 的下一个节点的编号，比要加入的节点的编号大，说明位置找到。就是插入在temp 和 next 之间。
				break;
			}
			if (temp.next.no == newNode.no) {
				// 说明希望添加的节点编号已经存在
				flag = true;
				break;
			}
			// 向后移一位
			temp = temp.next;
		}
		// 判断flag的值，要添加的编号是否存在。
		if (flag) {
			System.out.printf("准备插入的英雄的编号 %d 已经存在，不能加入\n", newNode.no);
		} else {
			// 将新节点的下一个，指向当前节点的下一个。
			newNode.next = temp.next;
			// 把当前节点的下一个，指向新节点。
			temp.next = newNode;
		}
		return originalHead;
	}
	
	/**
	 * 【修改节点内容】
	 * 修改节点的信息，根据no编号来修改，即no编号不能改。
	 * <p>
	 * 说明：
	 * 1. 根据heroNode 的 no 来修改即可
	 */
	public static HeroNode update(HeroNode originalHead, HeroNode newNode) {
		// 1. 判断一下链表是否为空
		if (originalHead == null) {
			System.out.println("链表为空");
			return newNode;
		}
		if (newNode == null) {
			// System.out.println("要添加的节点为空");
			return originalHead;
		}
		
		HeroNode temp = originalHead;
		
		// 表示是否找到该节点
		boolean flag = false;
		// 说明已经遍历完了链表，直接退出循环。
		while (temp.next != null) {
			if (temp.no == newNode.no) {
				// 找到相同排名的节点。
				flag = true;
				break;
			}
			temp = temp.next;
		}
		// 判断是否存在要修改的编号。
		if (flag) {
			temp.name = newNode.name;
			temp.nickName = newNode.nickName;
		} else {
			System.out.printf("准备修改的英雄的编号 %d 不存在,不能修改这个英雄\n", newNode.no);
		}
		return originalHead;
	}
	
	/**
	 * 【删除节点】
	 * 思路：
	 * 1. 我们先找到需要删除的这个节点的前一个节点 temp
	 * 2. temp.next = temp.next.next
	 * 3. 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收。
	 * @param no 要删除的节点的编号
	 */
	public static HeroNode delete(HeroNode originalHead, int no) {
		// 1. 判断一下链表是否为空
		if (originalHead == null) {
			System.out.println("链表为空");
			return null;
		}
		if (no <= 0) {
			System.out.println("参数不合法");
			return originalHead;
		}
		
		HeroNode temp = originalHead;
		boolean flag = false;
		
		while (temp.next != null) {
			if (temp.next.no == no) {
				// 找到要删除的节点
				flag = true;
				break;
			}
			// 后移
			temp = temp.next;
		}
		
		// 判断flag
		if (flag) {
			// 找到节点
			temp.next = temp.next.next;
		} else {
			System.out.printf("准备删除的英雄的编号 %d 不存在,不能删除这个英雄\n", no);
		}
		return originalHead;
	}
	
	/**
	 * 【遍历链表】
	 * 通过一个辅助变量遍历，帮助遍历整个链表。
	 */
	public static void list(HeroNode originalHead) {
		// 判断链表是否为null
		if (originalHead == null) {
			System.out.println("链表为空");
			return;
		}
		// 链表不为null,因为head节点不能动。创建一个temp辅助变量，来遍历链表
		HeroNode temp = originalHead;
		while (temp.next != null) {
			// 输出节点的信息
			System.out.println(temp);
			// 将temp后移，一定小心。
			temp = temp.next;
		}
	}
	
	/**
	 * 【统计有效节点个数】
	 * 获取到单链表的节点的个数(如果是带头节点的链表，不统计头节点)
	 * @return 有效节点的数量
	 */
	public static int getCount(HeroNode originalHead) {
		// 判断链表是否为null
		if (originalHead == null) {
			System.out.println("链表为空");
			return 0;
		}
		int count = 0;
		
		// 链表不为null，因为head节点不能动。创建一个temp辅助变量，来遍历链表
		// 头结点不包含数据，不统计在内。
		HeroNode temp = originalHead;
		while (temp.next != null) {
			// 有效节点+1
			count++;
			// 将temp后移，一定小心。
			temp = temp.next;
		}
		return count;
	}
	
	/**
	 * 【按索引正序号查找】
	 * @param index 索引
	 * @return 节点对象
	 */
	public static HeroNode getHeroNodeByIndexAsc(HeroNode originalHead, int index) {
		// 判断链表是否为null
		if (originalHead == null) {
			System.out.println("链表为空");
			return null;
		}
		if (index <= 0) {
			System.out.println("索引参数不合法");
			return null;
		}
		HeroNode temp = originalHead;
		int count = getCount(originalHead);
		
		if (index > count) {
			System.out.println("索引超出了链表总节点数。");
			return null;
		}
		for (int i = 0; i < index; i++) {
			temp = temp.next;
		}
		return temp;
	}
	
	/**
	 * 【按索引反序查找】
	 * @param index 索引
	 * @return 节点对象
	 */
	public static HeroNode getHeroNodeByIndexDesc(HeroNode originalHead, int index) {
		// 判断链表是否为null
		if (originalHead == null) {
			System.out.println("链表为空");
			return null;
		}
		if (index <= 0) {
			System.out.println("索引参数不合法");
			return null;
		}
		HeroNode temp = originalHead;
		int count = getCount(originalHead);
		
		if (index > count) {
			System.out.println("索引超出了链表总节点数。");
			return null;
		}
		// 正数第 = 总共 - 倒数第i
		int asc = count - index;
		for (int i = 0; i <= asc; i++) {
			temp = temp.next;
		}
		return temp;
	}
	
	/**
	 * 【反转整条链表】
	 * @return 返回反转后的头节点
	 */
	public static HeroNode reverse(HeroNode originalHead) {
		// 判断链表是否为空 或者只有一个有效节点，无需反转
		if (originalHead == null) {
			return null;
		}
		HeroNode next = originalHead.next;
		HeroNode cur = originalHead;
		
		cur.next = null;
		
		while (next != null) {
			// 将next的下个节点，赋值给temp
			HeroNode temp = next.next;
			// 将当前节点赋值给next的下个节点。
			next.next = cur;
			// 再将next赋值给当前节点。
			cur = next;
			// 将temp赋值给next
			next = temp;
		}
		return cur;
	}
	
	/**
	 * 【反转链表中指定区域的节点】
	 * @param originalHead 原始节点
	 * @param m            起始位置 1 ≤ m ≤ n ≤ 链表长度。
	 * @param n            结束位置 1 ≤ m ≤ n ≤ 链表长度。
	 * @return 返回反转之后的链表
	 */
	public static HeroNode reverseBetween(HeroNode originalHead, int m, int n) {
		if (originalHead == null) {
			return null;
		}
		int length = getCount(originalHead);
		if (m <= 0 || n <= 0 || m > n || m > length || n > length) {
			System.out.println("参数不合法");
		}
		
		// 新建一个头节点，下一个指向原始节点。
		HeroNode pstart = new HeroNode(0, "", "");
		pstart.next = originalHead;
		// 获取尾部不需要反转的节点。
		HeroNode temp1 = pstart;
		for (int i = 0; i < n; i++) {
			temp1 = temp1.next;
		}
		HeroNode ptail = temp1.next;
		temp1.next = null;
		
		// 获取需要反转的节点之前的一个节点。
		HeroNode temp2 = pstart;
		for (int i = 0; i < m - 1; i++) {
			temp2 = temp2.next;
		}
		// 得到需要反转的头节点。
		HeroNode newHead = temp2.next;
		temp2.next = null;
		
		// 定义一个当前节点。
		HeroNode cur = newHead;
		while (cur != null) {
			// 将当前节点的下一个节点，备份
			HeroNode temp3 = cur.next;
			// 将尾巴赋值给当前节点的下一个
			cur.next = ptail;
			// 将当前节点赋值给尾巴
			ptail = cur;
			// 将当前节点移到下一个。
			cur = temp3;
		}
		// 将尾巴赋值给newHead。
		newHead = ptail;
		// 再将newHead拼接到原节点上。
		temp2.next = newHead;
		// 返回 pstart.next
		return pstart.next;
	}
	
	/**
	 * 【递归反转】
	 * @param originalHead 原始节点
	 * @param m            起始位置 1 ≤ m ≤ n ≤ 链表长度。
	 * @param n            结束位置 1 ≤ m ≤ n ≤ 链表长度。
	 * @return 返回反转之后的链表
	 */
	public static HeroNode recursionReverseBetween(HeroNode originalHead, int m, int n) {
		if (originalHead == null) {
			return null;
		}
		int length = getCount(originalHead);
		if (m <= 0 || n <= 0 || m > n || m > length || n > length) {
			System.out.println("参数不合法");
		}
		if (m == 1) {
			return reverse(originalHead, n);
		}
		originalHead.next = recursionReverseBetween(originalHead.next, m - 1, n - 1);
		return originalHead;
	}
	
	private static HeroNode successor = null;
	
	private static HeroNode reverse(HeroNode head, int n) {
		if (head == null) {
			return null;
		}
		if (n == 1) {
			successor = head.next;
			return head;
		}
		HeroNode last = reverse(head.next, n - 1);
		head.next.next = head;
		head.next = successor;
		return last;
	}
	
	/**
	 * 逆序打印输出链表
	 */
	public static void reverseOrderList(HeroNode originalHead) {
		// 判断链表是否为空 或者只有一个有效节点，无需反转
		if (originalHead == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode temp = originalHead;
		// 创建一个栈(先进后出)，将各个节点，压入栈中。
		Stack<HeroNode> stack = new Stack<>();
		while (temp != null) {
			stack.push(temp);
			temp = temp.next;
		}
		// pop()弹出
		while (stack.size() > 0) {
			System.out.println(stack.pop());
		}
	}
	
	/**
	 * 【排序——插入排序】
	 * 算法中是直接交换节点，时间复杂度 O（n^2）, 空间复杂度 O（1）
	 */
	public static HeroNode insertionSortList(HeroNode originalHead) {
		if (originalHead == null || originalHead.next == null) {
			return originalHead;
		}
		// 用于遍历链表的临时节
		HeroNode p = originalHead.next;
		// 定义一个新节点 始终将 originalHead 作为下一个节点。
		HeroNode pstart = new HeroNode(0, "", "");
		// 用于记录 P 已经遍历到哪个节点。方便 P 后移到下一个。
		HeroNode pend = originalHead;
		// 为了操作方便，将pstart.next永远指向head这个头结点。
		pstart.next = originalHead;
		while (p != null) {
			// 临时节点，每次都是从head开始遍历，跟 p 对比两个节点的值。
			HeroNode temp = pstart.next;
			// 用于记录temp的前一个位置的节点。等需要交换 p 节点位置的时候使用。
			HeroNode pre = pstart;
			// 遍历查找插入位置
			while (temp != p && p.no >= temp.no) {
				// 当 temp != p 并且，p.no >= temp.no 时 pre 往后移一位。
				temp = temp.next;
				pre = pre.next;
			}
			// 当 temp == p 时
			if (temp == p) {
				// 把 pend 指到 p 位置。然后将 pend.next 赋值给 p 再去遍历。
				pend = p;
			} else {
				// p.no < temp.no 时，说明找到了要插入的位置。
				// 插入在 temp 的前面 pre 的后面。
				// 因为 p 要被移到前面去。所以先将 p 后面的都赋值给pend.next.
				pend.next = p.next;
				// 把 temp 放在 p 后面
				p.next = temp;
				// 把 p 放在 pre后面
				pre.next = p;
			}
			// p 后移一位
			p = pend.next;
		}
		originalHead = pstart.next;
		return originalHead;
	}
	
	/**
	 * 【排序——递归插入排序】
	 * 采用递归进行插入排序
	 */
	public static HeroNode recursionInsertionSortList(HeroNode newHead) {
		if (newHead == null || newHead.next == null) {
			return newHead;
		}
		// 新建一个慢节点
		HeroNode slow = newHead;
		// 新建一个快节点
		HeroNode fast = newHead;
		// 循环快节点的下一个 下一个的下一个都不为null
		while (fast.next != null && fast.next.next != null) {
			// 将慢节点后移一位。
			slow = slow.next;
			// 将快节点后移两位。
			fast = fast.next.next;
		}
		// 当快节点的下一个或者下一个的下一个为null时。
		// 将链表从慢节点的后面断开。
		HeroNode temp = slow.next;
		slow.next = null;
		
		// 递归将左右两个链表断开。直到最后仅有一个节点。
		HeroNode left = recursionInsertionSortList(newHead);
		HeroNode right = recursionInsertionSortList(temp);
		// 调用方法合并节点。
		return recur(left, right);
	}
	
	/**
	 * 【递归合并有序链表】
	 * 按顺序合并
	 * @param l1 节点1
	 * @param l2 节点2
	 * @return 返回合并后的节点
	 */
	public static HeroNode recur(HeroNode l1, HeroNode l2) {
		// 判断是否为null
		if (l1 == null && l2 == null) {
			return null;
		}
		if (l1 == null) {
			return l2;
		}
		if (l2 == null) {
			return l1;
		}
		
		// 新建头结点
		HeroNode head;
		
		// 如果l1.no <= l2.no，那么头结点的值为l1.head的值，然后开始递归
		if (l1.no <= l2.no) {
			head = l1;
			head.next = recur(l1.next, l2);
			
		} else {
			//否则，头结点的值为l2.head的值，然后开始递归
			head = l2;
			head.next = recur(l1, l2.next);
		}
		// 返回链表
		return head;
	}
	
	/**
	 * 【合并链表】
	 * 合并两个无序链表，成有序链表
	 */
	public static HeroNode mergeToOrderList(HeroNode l1, HeroNode l2) {
		if (l1 == null && l2 == null) {
			return null;
		}
		if (l1 == null) {
			return recursionInsertionSortList(l2);
		}
		if (l2 == null) {
			return recursionInsertionSortList(l1);
		}
		l1 = recursionInsertionSortList(l1);
		l2 = recursionInsertionSortList(l2);
		return recur(l1, l2);
	}
}